题解 SP64@洛谷 | PERMUT1@SPOJ 【PERMUT1 - Permutations】

本题是三倍经验 Link1 Link2，不知道为啥这几题难度评分不一样，区别只有多组数据和模数。

好了，下面进入正题。

题意简述：多组数据，给定 $n$，求 $1\sim n$ 的所有排列中逆序对个数恰有 $k$ 个的情况。

由于有多组数据，因此考虑预处理出所有情况后进行 $O(1)$ 查询，虽然这题数据范围较小好像也不用。

怎么进行预处理呢？考虑进行动态规划。

设计状态 $dp_{i,j}$ 表示对于 $1\sim i$ 的所有排列，恰有 $j$ 个逆序对的情况总数。

考虑如何进行转移。我们在 $1\sim i-1$ 的一个排列，添加一个数 $i$，此时我们可以使逆序对个数增加 $1,2,\cdots,i-1$ 个。因此，我们可以得到转移方程：

$dp_{i,j}=\sum_{k=0}^{i-1}dp_{i-1,j-k}$

此时，根据我们状态的定义，$dp_{n,k}$ 即为所求。

这是我们注意到一个问题：这个转移是 $O(n^3)$ 的，无法通过上面两道双倍经验，因此需要优化。

看到我们最后一维要加的是一个区间内的 $dp$ 值，容易想到通过维护前缀和来优化时间。我们采取循环中滚动求前缀和的方式。

代码中的前缀和开的是数组，也有只用一个变量的做法（其实并不难），因为我懒，这里就不写了。

另外，由于数量可能很大，需要开 long long。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1005;

ll T, n, m;
ll dp[N][N] = {{0}, {1}}, s[N];

void dpInit() {
	for(ll i=2;i<=1000;i++) {
		memset(s, 0, sizeof(s));
		for(ll j=0;j<=1000;j++) {
			s[j] = dp[i-1][j];
			if(j) s[j] += s[j-1];
			dp[i][j] = s[j];
			ll _ = j - i + 1;
			if(_ >= 0) s[j] -= dp[i-1][_];
		}
	}
}

int main() {
	dpInit();
	scanf("%lld", &T);
	while(T--) {
		scanf("%lld%lld", &n, &m);
		printf("%lld\n", dp[n][m]);
	}
	return 0;
}